package LearnDataStructure.d_图结构.b_拓扑排序;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 15:23
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
public class c_拓扑排序byDFSand回溯and标记 {
    public static void main(String[] args) {
        c_拓扑排序byDFSand回溯and标记 test = new c_拓扑排序byDFSand回溯and标记();
        test.useTopologicalSort();
    }

    public void useTopologicalSort() {
        String[] nodes = {"a","b","c","d"};//nodes与graph的元素顺序是有讲究的
        int[][] graph = {
              //a   b  c  d
                {0, 1, 0, 0},//a
                {0, 0, 0, 0},//b
                {0, 1, 0, 0},//c
                {0, 0, 1, 0},//d
        };
        N = nodes.length;
        visited = new int[N];
        result = new int[N];
        currentSet = N;
        useTopologicalSort(nodes,graph);

        for (int i = 0; i < N; i++) {
            System.out.print(nodes[result[i]] + " ");
        }
    }

    private int N = 0;
    private int[] visited = null;
    private int[] result = null;
    private int currentSet = 0;

    public void useTopologicalSort(String[] nodes, int[][] graph) {
        for (int row = 0; row < N; row++) {//每一个节点都进行一次DFS
            if (visited[row] == 1) {//如果被标记上"我已经被使用了"
                continue;//那就跳过
            }
            boolean currentNode = TopologicalSort(row, nodes, graph);
            if (!currentNode) {//如果有一次结果返回了false，那就代表有环
                System.out.println(false);//直接返回false
                return;
            }
        }
    }

    /**
     * 能处理有环的图
     * @param row
     * @return
     */
    public boolean TopologicalSort(int row, String[] nodes, int[][] graph) {
        visited[row] = -1;//当前传入的节点A，是靠坐标传入的，那就把当前坐标代表的节点打上“正在使用的标记”
        for (int col = 0; col < N; col++) {//遍历所有可能，遍历所有其他节点
            if (graph[row][col] > 0) {//如果对其它节点确实有连通
                if (visited[col] < 0) {//如果这个节点B,被打上过“正在使用的标记”
                    return false;//就代表再一次遍历中两次拜访了B(当前是第二次拜访),那就有环！所以直接退出，没有拓扑排序！
                }
                if (visited[col] == 0 && !TopologicalSort(col,nodes,graph)) {//B没有被标记，那就递归，以B为出发点去遍历所有可能
                    return false;//如果B出发发现有环或者其他情况导致没有拓扑排序，那么A也就没有拓扑排序
                }
            }
        }
        //跳出循环；只要到这里，就代表遍历到了尽头；此节点A就要被放入拓扑数组中
        result[--currentSet] = row;//放入拓扑数组中；因为currentSet一开始是==result.length，所以必须--currentSet而不是currentSet--
        visited[row] = 1;//A打上"我已经被使用了"的标记
        return true;
    }
}
